#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        vector<int> ret;
        int lens = s.size(), lenword = words[0].size(),wordcount=words.size();
        //统计需要的字符数量
        int totallen=lenword*wordcount;

        if (lens < totallen)return ret;
        unordered_map<string, int> wordfque;

        for (auto &x : words)
            wordfque[x]++;

        for (int i = 0; i < lenword; i++)
        {
            unordered_map<string,int> windowfque;
            int left=i,right=i,count=0;
            while(right+lenword<=lens)
            {
                string sw=s.substr(right,lenword);
                right+=lenword;

                if(wordfque.find(sw)!=wordfque.end())
                {
                    windowfque[sw]++;
                    count++;
                    //如果窗口内的某个字符串数量多与word，从左窗口开始移除
                    while(windowfque[sw]>wordfque[sw])
                    {
                        string leftword=s.substr(left,lenword);
                        windowfque[leftword]--;
                        count--;
                        left+=lenword;
                    }
                    if(count==wordcount)ret.push_back(left);
                }
                else
                {
                    windowfque.clear();
                    count=0;
                    left=right;
                }
            }
        }
        return ret;
    }
};
int main()
{
    string s1 = "wordgoodgoodgoodbestword";
    vector<string> s2 = {"wordfque","good","best","wordfque"};
    auto ret = Solution().findSubstring(s1, s2);
    for (auto &x : ret)
    {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}